A compact, idiomatic BFS on adjacency lists. This implementation returns the `parent` and `level` for each reachable vertex.

  • The core principle is to enqueue on first discovery and process nodes in the order they were found.
  • Using a `set` for `visited` provides efficient O(1) average time complexity for checking if a node has been seen.
  • A `deque` (double-ended queue) from the `collections` module is highly optimized for fast appends and pops from both ends.
  • This template ensures that we never enqueue a visited node again, preventing redundant processing and infinite loops in graphs with cycles.
bfs_template.py Python 

# Inputs:
#   G: dict mapping vertex -> iterable of neighbor vertices (adjacency list)
#   s: start vertex in G
# Returns:
#   (parent, level) dicts for each reachable vertex from s

from collections import deque
def bfs(G, s):
    # Initialize metadata for all vertices
    parent = {v: None for v in G}
    level  = {v: float('inf') for v in G}
    level[s] = 0
    # Use deque for O(1) pops from the left; visited set prevents re-enqueue
    q, visited = deque([s]), {s}
    # BFS main loop: process vertices in discovery order
    while q:
        u = q.popleft()
        for w in G[u]:
            if w not in visited:
                visited.add(w)
                parent[w] = u
                level[w] = level[u] + 1
                q.append(w)
    return parent, level